/**
 * 子数组的最大平均数
 * 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
 * 请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
 * 任何误差小于 10-5 的答案都将被视为正确答案。
 */

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function(nums, k) {
    /**
     * 滑动窗口
     * 1. 先计算前 k 个元素的和
     * 2. 从 k 开始，每次减去前一个元素，加上当前元素
     * 3. 每次比较最大值
     * 4. 返回最大值除以 k
     * 时间复杂度：O(n)S
     */
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += nums[i];
    }
    let maxSum = sum;
    for (let i = k; i < nums.length; i++) {
        sum = sum - nums[i - k] + nums[i];
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum / k;
};

// console.log(findMaxAverage([1,12,-5,-6,50,3], 4)); // 12.75
// console.log(findMaxAverage([5], 1)); // 5
console.log(findMaxAverage([0,1,1,3,3], 4)); // 4

// 暴力解法 时间复杂度：O(n^2)
// var findMaxAverage = function(nums, k) {
//     if (nums.length === 1) return nums[0]
//     let averArr = []
//     for (let i = 0;i <= nums.length - k;i ++) {
//         let sum = nums[i];
//         for (let j = i + 1;j < i + k;j ++) {
//             sum += nums[j];
//         }
//         averArr.push(sum / k);
//     }
//     return Math.max(...averArr);
// };